package gold.gold02;

/**
 * 简单
 * 100, 大家时间都是1。就只能这么写了吧。
 */
public class S0404检查平衡性 {
    public boolean isBalanced(TreeNode root) {
        return isBalance(root).isBalance();
    }
    // 只需要知道左右子树的深度, 然后返回深度和是否是平衡的就行了
    // 我一直不知道这种子函数怎么直接用循环的方式写到主函数里
    public S0404resultType isBalance(TreeNode node){
        if(node == null) return new S0404resultType(0, true);
        S0404resultType temp1 = isBalance(node.left);
        S0404resultType temp2 = isBalance(node.right);
        return new S0404resultType(Math.max(temp1.getDepth(), temp2.getDepth()) + 1,
                temp1.isBalance() && temp2.isBalance() && Math.abs(temp1.getDepth() - temp2.getDepth()) < 2);
    }
    // 内部类, 这个类其实可以用一个int[]来代替。内部类中的private字段可以被外部类访问到
    class S0404resultType{
        private int depth;
        private boolean isBalance;

        public S0404resultType() {
        }
        public S0404resultType(int depth, boolean isBalance) {
            this.depth = depth;
            this.isBalance = isBalance;
        }
        public int getDepth() {
            return depth;
        }
        public boolean isBalance() {
            return isBalance;
        }

        @Override
        public String toString() {
            return super.toString();
        }
    }

    // 这样就不用写一个子类了, 但是我觉得没有我写得好, 因为这个depth操作就已经遍历了一遍了,
    // 这个复杂度是n*n, 我的复杂度是n, 虽然大家时间都是1。这个解法很不合适。
    // 比如添加一个depth为-1表示子树非平衡。
    public boolean isBalanced2(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        return isBalanced2(root.left) && isBalanced2(root.right);
    }

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}
